package com.example.demo.arithmetic;

import java.util.Stack;

/**
 * Description: 括号匹配问题<br/>
 *
 * @author <br/>;
 * @taskId <br/>
 * @Date 2019/5/14 14:25
 * @Version 1.0
 */
public class BracketsMatch {

    /**
     * 遇到左括号入栈，遇到右括号时先检查栈是否为空，若空则返回false，若不空则弹出栈顶元素看与右括号是否匹配。
     * 所有元素处理完后若栈为空则说明匹配成功，否则匹配不成功。
     *
     * @param s
     * @return
     */
    public static boolean isValidate(String s) {
        Stack<Character> a = new Stack<Character>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(') {
                a.push(')');
            }
            if (c == '[') {
                a.push(']');
            }
            if (c == '{') {
                a.push('}');
            }
            if (c == ')' || c == ']' || c == '}') {
                if (a.size() == 0) {
                    return false;
                }
                if (a.pop() != c) {
                    return false;
                }
            }
        }
        if (a.size() != 0) {
            return false;
        }
        return true;
    }

    //(())
    public static int getLength(String s) {
        int count = 0, max = 0;
        for (int i = 0; i < s.length(); i++) {
            if ('(' == s.charAt(i)) {
                count++;
            } else {
                count--;
            }
            max = Math.max(count, max);
        }
        return max;
    }

    public static void main(String[] args) {
        //判断括号匹配问题
        String s = "()()";
        boolean a = isValidate(s);
        int length = getLength("(())(((())");
        System.out.println(a);
        System.out.println(length);
    }

}
